import java.util.ArrayList;
import java.util.LinkedList;

/**
 * Created by ospip on 2017/10/26.
 * Copyright (c) 2017 LLAP. All rights reserved.
 */
public class Tree<T extends Comparable<? super T>> {
    public ArrayList<TreeNode<T>> nodes;
    public ArrayList<LinkedList<Integer>> nodeGraph;
    //public TreeNode<T> root; // root == nodes[0]

    public Tree() {
        nodes = new ArrayList<>();
        nodeGraph = new ArrayList<>();
    }

    public Tree(T[] dataSet) {
        this();
        for (T i : dataSet) {
            this.addNode(i);
        }
    }

    public Tree(Tree<T> t) {
        this();
        for (TreeNode<T> i : t.nodes) {
            this.nodes.add(i);
        }
        for (int i = 0; i < t.nodes.size(); i++) {
            this.nodeGraph.add(new LinkedList<>());
            for (Integer j : t.nodeGraph.get(i)) {
                this.nodeGraph.get(i).add(j);
            }
        }
    }

    public Tree(TreeNode<T> root) {
        this();
        nodes.add(new TreeNode<>(root.data));
        nodeGraph.add(new LinkedList<>());
    }

    public Tree<T> addNode(T data) {
        nodes.add(new TreeNode<>(data));
        nodeGraph.add(new LinkedList<>());
        return this;
    }

    public Tree<T> set(int index, T data) {
        nodes.get(index).data = data;
        return this;
    }

    public Tree<T> setParent(int index, int pIndex) {
        // pIndex -> index
        nodeGraph.get(pIndex).addFirst(index);
        return this;
    }

    public Tree<T> setChild(int index, int cIndex) {
        // index -> cIndex
        nodeGraph.get(index).addFirst(cIndex);
        return this;
    }

    public void leafToRoot() {
        dfs(0, new boolean[nodes.size()], "");
        System.out.println();
    }

    public void dfs(int index, boolean[] vis, String path) {
        if (vis[index]) return; // 这句好像并用不着但是还是先加上吧
        path += nodes.get(index).toString() + "";
        if (nodeGraph.get(index).isEmpty()) {
            // 判断叶节点
            System.out.println(path);
            return;
        }
        vis[index] = true;
        for (Integer i : nodeGraph.get(index)) {
            // 遍历子节点
            dfs(i, vis, path + " -> ");
        }
        vis[index] = false;
    }

    public static<T> void leafToRoot(Tree<? super T> tree) {
        tree.leafToRoot();
    }

    public static void main(String[] args) {
        String[] a = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N"}; // 14
        Tree<String> t = new Tree<>(a);
        /*t.setChild(0, 1);
        t.setChild(0, 2);
        t.setChild(0, 3);
        t.setChild(1, 4);
        t.setChild(1, 5);
        t.setChild(2, 6);
        t.setChild(3, 7);
        t.setChild(3, 8);
        t.setChild(3, 9);
        t.setChild(8, 10);
        t.setChild(10, 11);
        t.setChild(10, 12);*/
        t.setChild(0, 1).setChild(0, 2).setChild(0, 3);
        t.setChild(1, 4).setChild(1, 5);
        t.setChild(3, 6).setChild(6, 7).setChild(6, 8);
        t.setChild(3, 9);
        t.leafToRoot();
        //Tree<String> t2 = new Tree<>(t);
        //t2.leafToRoot();
    }
}
